package com.martain.leetcode.t105;

import com.martain.leetcode.common.TreeNode;

import java.util.HashMap;

public class t105 {
//    前序遍历 preorder = [3,9,20,15,7]
//    中序遍历 inorder = [9,3,15,20,7]

    /**
     * 构建树
     * @param preorder 先序遍历
     * @param inorder  中序遍历
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 先序遍历第一个数是根节点
        if (preorder.length==0||inorder.length == 0) return null;
        HashMap<Integer,Integer> inMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inMap.put(inorder[i],i );
        }
        TreeNode treeNode = _buildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1, inMap);
        return treeNode;
    }

    public TreeNode _buildTree(int[] preorder, int pstart, int pend, int[] inorder, int istart, int iend, HashMap<Integer, Integer> inMap){
        if (pstart>pend||istart>iend) return null;
        TreeNode root = new TreeNode(preorder[pstart]);
        int rootIndex = inMap.get(root.val);
        int leftNumber = rootIndex-istart;
        root.left = _buildTree(preorder,pstart+1,pstart+leftNumber,inorder,istart,rootIndex-1,inMap);
        root.right = _buildTree(preorder,pstart+leftNumber+1,pend,inorder,rootIndex+1,iend,inMap);
        return root;
    }

    public static void main(String[] args) {
//        int[] preorder =new int[]{3,9,20,15,7};
//        int[] inorder = new int[]{9,3,15,20,7};
        int[] preorder =new int[]{1,2,3};
        int[] inorder = new int[]{2,3,1};
        t105 t105 = new t105();
        t105.buildTree(preorder,inorder);
    }
}
